package com.gaogzhen.algorithms4.foundation;

/**
 *  动态连通性quick-find算法
 */
public class QuickFindUF extends AbstractUnionFind{

    /**
     * 初始化触点数量
     * {@code n} elements {@code 0} through {@code n-1}.
     *
     * @param  n 初始化触点数量{@code n}
     */
    public QuickFindUF(int n) {
        super(n);
    }


    /**
     * 返回触点p所在的分量标志
     *
     * @param  p 触点p
     * @return {@code p}所在分量的标志
     */
    @Override
    public int find(int p) {
        validate(p);
        return getId(p);
    }



    /**
     * 合并触点p和触点q
     * @param p 触点q
     * @param q 触点q
     */
    @Override
    public void union(int p, int q) {
        validate(p);
        validate(q);
        int pID = getId(p);   // needed for correctness
        int qID = getId(q);   // to reduce the number of array accesses

        // p and q are already in the same component
        if (pID == qID) return;
        int n = capacity();
        for (int i = 0; i < n; i++)
            if (getId(i) == pID) setId(i, qID);
        decreaseCount();
    }
}